package ChainTable;


/**
 * 单链表
 * 火车类,是由多个车厢类拼接在一起
 */
public class SingleLinkedList {
    // 当前火车中车厢的节点个数(实际就是具体元素的个数)
    private int size;
    // 当前火车的火车头
    private Node head;

    /**
     * 在火车头部添加元素-添加一个车厢节点
     * void addFirst(int val)
     * 在火车尾部添加元素-添加一个车厢节点
     * void addLast(int val)
     * 在火车任意位置添加元素-添加一个车厢节点
     * void addIndex(int index,int val)
     *
     * @param val
     */
    public void addFirst(int val) {
        // 新建一个车厢节点
        Node node = new Node(val);
        // 判断当前的火车是否为空
        if (this.head == null) {
            this.head = node;
        } else {
            // 火车中有节点，要把当前新车厢挂载到火车头部
            node.next = this.head;
            this.head = node;
        }
        size++;
    }

    public void addIndex(int index, int val) {
        if (index < 0 || index > size) {
            System.err.println("add index illegal!");
            return;
        }

        if (index == 0) {
            addFirst(val);
            return;
        }
        Node node = new Node(val);
        Node prev = head;
        for (int i = 0; i < index - 1; i++) {
            prev = prev.next;
        }
        node.next = prev.next;
        prev.next = node;
        size++;
    }

    public void addLast(int val) {
        addIndex(size, val);
    }

    /**
     *
     * 删除操作
     * 根据索引删除相应节点
     * void removeIndex(int index)
     * 删除头节点
     * void removeFirst()
     * 删除尾节点
     * void removeLast()
     * 删除链表中第一次值为val的节点
     * void removeValueOnce(int val)
     * 删除链表中所有值为val的节点
     * void removeValueAll(int val)
     *
     * @param index
     */
    public void removeIndex(int index) {
        if (rangeCheck(index)) {
            if (index == 0) {
                Node temp = head;
                head = head.next;
                temp.next = null;
                size--;
            } else {
                Node prev = head;
                for (int i = 0; i < index - 1; i++) {
                    prev = prev.next;
                }
                Node cur = prev.next;
                prev.next = cur.next;
                cur.next = null;
                size--;
            }
        } else {
            System.out.println("remove index illegal!");
        }
    }

    public void removeFirst() {
        removeIndex(0);
    }

    public void removeLast() {
        removeIndex(size - 1);
    }
    /**
     * 根据用户输入的index查找对应值
     * int get(int index)
     * @param index
     * @return
     */
    public int get(int index){
        if (rangeCheck(index)){
            Node prev= head;
            for (int i = 0; i < index; i++) {
                prev=prev.next;
            }
            return prev.val;
        }else{
            System.out.println("get index illegal!");
            return -1;
        }
    }
    /**
     * 判断当前链表中是否包含值为val的节点
     * boolean contains(int val)
     * @param val
     * @return
     */
    public boolean contains(int val){
        for (Node temp = head;temp!=null;temp=temp.next){
            if (temp.val==val){
                return true;
            }
        }
        return false;
    }
    /**
     * 将单链表中索引为index的节点值改为newVal
     * int set(int index,int newVal)
     * @param index
     * @param newVal
     * @return 修改前的值
     */
    public int set(int index,int newVal){
        if (rangeCheck(index)){
            Node node = head;
            for (int i = 0; i < index; i++) {
                node=node.next;
            }
            int oidValue=node.val;
            node.val=newVal;
            return oidValue;
        }else{
            System.out.println("set index illegal!");
            return -1;
        }
    }
    public void removeValueOnce(int val) {
        if (head != null && head.val == val) {
            removeFirst();
        } else {
            Node prev = head;
            while (prev.next != null) {
                if (prev.next.val == val) {
                    Node cur = prev.next;
                    prev.next = cur.next;
                    cur.next = null;
                    size--;
                    return;
                } else {
                    prev = prev.next;
                }
            }
        }
    }

    public void removeValueAll(int val) {
        while (head != null && head.val == val) {
          removeFirst();
        }
        if (head == null) {
            return;
        } else {
            Node prev = head;
            while (prev.next != null) {
                if (prev.next.val == val) {
                    Node cur = prev.next;
                    prev.next = cur.next;
                    cur.next = null;
                    size--;
                }else {
                    prev = prev.next;
                }
            }
        }
    }

    public String toString() {
        String ret = "";
        // 遍历火车这个类，
        // 从火车头(head)走到火车尾部
        // 暂时存储当前头节点地址
        Node node = head;
        while (node != null) {
            ret += node.val;
            ret += "->";
            // 继续访问下一节车厢
            node = node.next;
        }
        ret += "NULL";
        return ret;
    }

    /**
     * 检查是否索引是否规范
     *
     * @index
     */
    private boolean rangeCheck(int index) {
        if (index < 0 || index >= size) {
            return false;
        }
        return true;
    }
}


/**
 * 火车车厢类,一个车厢只能保存一个元素
 */
class Node {
    // 存储具体数据
    int val;
    // 保存下一个车厢的地址
    Node next;

    public Node(int val) {
        this.val = val;
    }
}